package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public long minimumMoney(int[][] transactions) {
        long ans = 0;
        long debt = 0;
        long maxBack = 0;
        long maxNeeded = 0;
        for (int i = 0; i < transactions.length; i++) {
            if (transactions[i][0] > transactions[i][1]) {
                debt += transactions[i][0] - transactions[i][1];
                maxBack = Math.max(maxBack, transactions[i][1]);
            }
            else maxNeeded = Math.max(maxNeeded, transactions[i][0]);
        }
        ans = debt + Math.max(maxBack, maxNeeded);
        return ans;
    }

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int mod = (int) 1e9 + 7, len = group.length;
        long[] set = new long[2];
        long[][] dp = new long[n+1][minProfit+1];
        set[0] = 1L;
        dp[0][0] = 1;
        for (int i = 0; i < len; i++) {
            for (int j = n-group[i]; j >= 0; j--) {
                if ((set[j/64] & (1L << (j%64))) == 0) continue;
                for (int k = 0; k <= minProfit; k++) {
                    int p = Math.min(k + profit[i], minProfit);
                    dp[j+group[i]][p] = (dp[j+group[i]][p] + dp[j][k]) % mod;
                }
                set[(j+group[i])/64] |= (1L << ((j+group[i])%64));
            }
        }
        long m = 0;
        for (int i = 0; i <= n; i++) {
            m = (m + dp[i][minProfit]) % mod;
        }
        return (int) m;
    }

    private int sum_ = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root,0);
        return sum_;
    }
    public void dfs(TreeNode root,int sum){
        sum = sum*10 + root.val;
        if(root.left != null) dfs(root.left,sum);
        if(root.right != null) dfs(root.right,sum);
        if(root.left == null && root.right == null) sum_ += sum;
    }
}
